910 - TV Game/910.cpp

   1 /*
   2   Problem: 910 - TV Game
   3
   4   Author: Andrés Mejía-Posada
   5
   6   Method: Dynamic programming
   7
   8   Accepted.
   9  */
  10 #include <iostream>
  11 #include <set>
  12
  13 using namespace std;
  14
  15 int main(){
  16   int N;
  17   while (cin >> N){
  18     int g[N][2]; //g[i][j] = A donde me lleva el nodo i con la entrada j
  19     set<int> special;
  20     for (int i=0; i<N; ++i){
  21       char a, b, c, d;
  22       cin >> a >> b >> c >> d;
  23       a -= 'A', b -= 'A', c -= 'A';
  24       g[a][0] = b;
  25       g[a][1] = c;
  26       if (d == 'x'){
  27         special.insert(a);
  28       }
  29     }
  30     int m;
  31     cin >> m;
  32
  33     unsigned long long dp[m+1][N]; //dp[i][j] = cantidad de caminos de longitud i que terminan en el nodo j
  34     memset(dp, 0ULL, sizeof dp);
  35     dp[0][0] = 1ULL; //Para llegar al nodo A hay un solo camino
  36     for (int i=0; i<m; ++i){
  37       for (int j=0; j<N; ++j){
  38         dp[i+1][g[j][0]] += dp[i][j];
  39         dp[i+1][g[j][1]] += dp[i][j];
  40       }
  41     }
  42
  43     unsigned long long answer = 0;
  44     for (int i=0; i<N; ++i){
  45       if (special.count(i)){
  46         answer += dp[m][i];
  47       }
  48     }
  49     cout << answer << endl;
  50   }
  51   return 0;
  52 }